package LeetCodeHot100TopInterview;

//前缀树结构
class TrieNode_ {
    //节点后续节点
    TrieNode_[] nexts;
    //需要统计的指标
    //通过该字符个数
    int pass;
    //以该字符结尾个数
    int end;

    public TrieNode_() {
        this.pass = 0;
        this.end = 0;
        //26代表这个节点后续最多有26条路，分别对应26个小写字母
        nexts = new TrieNode_[26];
    }
}
public class Q208_Trie {
    //实现前缀树


    private TrieNode_ root;

    public Q208_Trie() {
        this.root = new TrieNode_();
    }

    public boolean search(String word) {
        char[] chars = word.toCharArray();
        TrieNode_ TrieNode = this.root;
        int index = 0;
        for (int i = 0; i < chars.length; i++) {
            //确定下标
            index = chars[i] - 'a';
            if (TrieNode.nexts[index] == null) return false;
            //TrieNode指针指到下一个节点
            TrieNode = TrieNode.nexts[index];
        }
        return TrieNode.end > 0;
    }


    //前缀树字符插入 O(n)
    public void insert(String word) {
        char[] chars = word.toCharArray();
        TrieNode_ TrieNode = this.root;
        TrieNode.pass++;
        int index = 0;
        for (int i = 0; i < chars.length; i++) {
            index = chars[i] - 'a';
            if (TrieNode.nexts[index] == null) {
                TrieNode.nexts[index] = new TrieNode_();
            }
            TrieNode = TrieNode.nexts[index];
            TrieNode.pass++;
        }
        TrieNode.end++;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        char[] chars = prefix.toCharArray();
        TrieNode_ trieNode_ = this.root;
        int index = 0;
        for (int i = 0; i < chars.length; i++) {
            index = chars[i] - 'a';
            if (trieNode_.nexts[index] == null){
                return false;
            }
            trieNode_ = trieNode_.nexts[index];
        }
        return true;
    }

}
